package com.leecode.section;

/**
 * <p>
 * 数组异或操作
 *
 * 给你两个整数，n 和 start 。
 *
 * 数组 nums 定义为：nums[i] = start + 2*i（下标从 0 开始）且 n == nums.length 。
 *
 * 请返回 nums 中所有元素按位异或（XOR）后得到的结果。
 *
 * 示例1：
 *      输入：n = 5, start = 0
 *      输出：8
 *      解释：数组 nums 为 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。
 *           "^" 为按位异或 XOR 运算符。
 *
 * 示例2:
 *      输入：n = 4, start = 3
 *      输出：8
 *      解释：数组 nums 为 [3, 5, 7, 9]，其中 (3 ^ 5 ^ 7 ^ 9) = 8.
 *
 * 示例3:
 *      输入：n = 1, start = 7
 *      输出：7
 *
 * 提示:
 *      1 <= n <= 1000
 *      0 <= start <= 1000
 *      n == nums.length
 *
 * </p>
 *
 * @author qingshan
 * @since 2020-09-18 09:04
 */
public class ArrXor06 {

    public static void main(String[] args) {

//        System.out.println(xorOpertion(5, 0));
        xorOpertionTest();

    }

    /**
     * 暴力破解法
     * @param n
     * @param start
     * @return
     */
    public static int xorOpertion(int n, int start){
        int res = 0;
        for(int i = 0; i < n; i++){
            res ^= start + 2*i;
        }
        return res;
    }

    /**
     * 使用异或的特性
     * 1) 0 ^ x = x
     * 2) x ^ x = 0
     * 3) 2x ^ (2x+1) = 1
     *
     * 上面暴力破解最终公式
     *      res ^= start + 2*i
     *      i=0,n=1  i=1,n=2     i=2,n=3     i=3,n=4           i=(n-1),n
     *      start ^ start + 2 ^ start + 4 ^ start + 6 ..... ^ start + 2*n-2
     *
     *      类比 2x ^ (2x+1) = 1  start的公式每次递增2， 那么处理右移一位
     * todo
     *
     *
     */
    public static void xorOpertionTest(){
        System.out.print("0^x: ");
        System.out.println(0^8);

        System.out.print("x^x: ");
        System.out.println(8^8);

        System.out.print("2x^(2x+1): ");
        System.out.println(8^(8+1));
    }
}
